演算法和行程排班:

RTOS多任務運行的實現實際上是靠CPU在許多任務之間轉換、調度。CPU只有一個，輪番服務於一系列任務中的某一個。多任務運行使CPU的利用率得到最大的發揮，並使應用程式模組化。在即時應用中，多任務化的最大特點是，開發人員可以將很複雜的應用程式層次化，而且應用程式將更容易設計與維護。 因此在多任務即時操作系統RTOS中涉及到任務調度，任務調度機制是嵌入式即時操作系統的一個重要概念，也是其核心技術。針對嵌入式即時系統任務的管理和調度的特點,在多任務即時內核結構中，多數採用的是基於優先順序的可搶佔式調度策略。系統為每一個任務分配一個優先順序，調度程式總是選擇優先順序最高的就緒任務運行。內核運行中頻繁地進行任務調度，調度速度緩慢時，會影響整個系統的回應速度和處理能力。因此，關於最高優先順序就緒任務的查找演算法是即時多任務系統的關鍵技術。

本文給出64個優先順序任務內核的不同最高優先順序就緒任務查找演算法，通過實例詳細闡明其原理，並分析了各個演算法的優缺點.

最高優先順序就緒任務查找演算法：順次檢索法 關於最高優先順序就緒任務的查找，有多種處理方法，其中最簡單最基本的方法是順次檢索。將所有的任務按照優先順序排隊，優先順序高的排在佇列前邊，優先順序低的排在佇列後邊。查找時從佇列的頭部開始，遇到的第一個就緒任務就是優先順序最高的就緒任務。假如即時系統共有n個任務，按照優先順序別的高低，順次存入數組Tb[n]中。當某一優先順序別的任務處於就緒態時，就在相應的佇列處置就緒態標誌。在系統進行任務調度的過程中，只要從佇列的頭部開始，依次查找就緒態標誌，找到的第一個具有就緒態標誌的任務就是優先順序別最高的就緒任務。該方法思路簡單，查找便利，但存在的缺點是不同優先順序任務查找時所需要的時間不同，系統中的任務數越多，且最高優先順序就緒任務越靠後，則查找速度越慢。

逐次比較法

可以發現，最高優先順序就緒任務是可以通過OSRdyG和OSRdyT [ ]求出來的，下面介紹一種普通的逐次比較，求最高優先順序就緒任務演算法。首先，從OSRdyG的最低位往最高位比較搜索，若為1停止，最高優先順序就緒任務就在此位對應的OSRdyT [n]中；然後找到OSRdyT[n]中為1的最低位，那麼就可以確定最高優先順序就緒任務。

其演算法描述如下：

 for(i=0;i<8;i++)      

{ if (OSRdyG & OSMap [i])

break; }

for(j=0;j<8;j++)

{

if (OSRdyT [i]& OSMap [j])

break; }

highprio=i<<3+j;

顯然，用迴圈程式實現不但複雜，更重要的是執行時間是不確定的，因為有時只需一個迴圈即可，而有時需要8個迴圈，不符合即時系統的確定性原則。為了加快即時系統的執行速度，可以採用查表方法進一步改進演算法

查表法:
為了減少以上演算法所造成的時間損耗以及不確定性。採用查表的方法實現最高優先順序就

緒任務的查找，在程式中事先建立一個存儲表，保存在數組OSUnMapT [255]中，存儲值表示OSRdyG和OSRdyT[n]的值相對優先順序別高三位和低三位的映射值。存儲值內容見表1。 例如，若OSRdyG的值為二進位00100100b，即0x24，則查OSUnMapT [OSRdyG]得到的值是2，它相應於OSRdyG中的第2位bit2，類似地，如果OSRdyT[2]的值是二進位11000010，即0xC2，則OSUnMapT[OSRdyT [2]]的值是1，即第1位bit1。於是就緒任務的最高優先順序就等於8進制21，即17（2*8+1）。 因此利用該表，可以用固定 的三條程式指令就計算出就緒任務最高優先順序的；計算就緒任務最高優先順序的演算法如下：

   high3 =OSUnMapT [OSRdyG];                                


   low3 =OSUnMapT[OSRdyT [high3]];                     


   highprio =(high3<<3)+low3;                          

兩種演算法對比可知，後者是用儲存空間來換取了執行時間；而對於一個操作系統，任務調度是十分頻繁的，這一點空間相對其換取回來的寶貴CPU時間是微不足道的。可以採用這種策略，從而使其實時系統性能得到大大的提高。 對具有相同優先順序的任務可以用時間片輪轉或者先進先出方式,來搶佔CPU。然後調度程式先檢查該任務當前是否處於運行狀態，如果該任務正佔用CPU，則不進行任務調度，調度程式退出；如果沒有佔用CPU，則進行任務調度，讓找到的最高優先順序的就緒任務開始運行。